package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created by 朱城委 on 2021/7/21.<br><br>
 *
 * 汉诺塔问题
 */
public class Interview8_6 {

    public static void main(String[] args) {
        Interview8_6 instance = new Interview8_6();

        List<Integer> listA = new ArrayList<>(Arrays.asList((int)'A', 1, 0));
        List<Integer> listB = new ArrayList<>(Collections.singletonList((int)'B'));
        List<Integer> listC = new ArrayList<>(Collections.singletonList((int)'C'));
        instance.hanota(listA, listB, listC);
        System.out.println(listC);
        System.out.println();

        listA = new ArrayList<>(Arrays.asList((int)'A', 2, 1, 0));
        listB = new ArrayList<>(Collections.singletonList((int)'B'));
        listC = new ArrayList<>(Collections.singletonList((int)'C'));
        instance.hanota(listA, listB, listC);
        System.out.println(listC);
        System.out.println();
    }

    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A, B, C, A.size());
    }

    private void move(List<Integer> A, List<Integer> B, List<Integer> C, int size) {
        if(size == 2) {
            int value = A.remove(A.size() - 1);
            C.add(value);
            int containerA = A.get(0);
            int containerC = C.get(0);
            System.out.println(value + ": " + (char) containerA + " -> " + (char) containerC);
            return ;
        }

        move(A, C, B, size - 1);
        move(A, B, C, 2);
        move(B, A, C, size - 1);
    }
}
